package base_Suanfa.dongtaiguihua;

import java.util.Scanner;

//两个字符串的最短编辑距离
public class bianji_juli {
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        String a=scanner.nextLine();
        String b=scanner.nextLine();
        System.out.println(minDistance(a,b));
    }

    public static int minDistance(String word1, String word2) {
        int m=word1.length();
        int n=word2.length();
        int temp[][]=new int[m+1][n+1];
        for(int i=0;i<m;i++){
            temp[i][0]=i;      //初始化word1第一个元素
        }
        for(int j=0;j<n;j++){
            temp[0][j]=j;    //初始化word2的第二个元素
        }
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                temp[i][j]=Math.min(temp[i][j-1]+1,temp[i-1][j]+1);      //判断是加入还是删除一个点更好
                if(word1.charAt(i)!=word2.charAt(j)){
                    temp[i][j]=Math.min(temp[i][j],temp[i-1][j-1]+1);   //如果word1 中i位置和word2中j位置不匹配，那么就替换,操作就加1
                }
                else {
                    temp[i][j]=Math.min(temp[i][j],temp[i-1][j-1]); //如果word1 中i位置和word2中j位置匹配,就不操作
                }
            }
        }
        return temp[m-1][n-1];
    }
}
